package 算法.leetcode.sort;

import com.alibaba.fastjson.JSON;

/**
 * @author liclong
 * @create 2020-09-22 15:01
 * @desc 快排
 **/
public class QuickSort {
    public static void main(String[] args) {
        int[] array = new int[]{2, 3, 1, 7, 4, 9, 6};
        quickSort(array, 0, array.length - 1);
        System.out.println(JSON.toJSONString(array));
    }

    /**
     * 快速排序【原地】,【不稳定】,【[O(nlogn),O(n2)]】
     *
     * T(n) 在大部分情况下的时间复杂度都可以做到 O(nlogn)，
     * 只有在极端情况下(有序)，才会退化到 O(n2)
     * @param array
     * @param p
     * @param r
     */
    public static void quickSort(int[] array, int p, int r) {
        // 无法再分的时候排序结束
        if (p >= r) {
            return;
        }
        // 选取分区点
        int q = partition(array, p, r);
        // 处理分区点左侧的数据
        quickSort(array, p, q - 1);
        // 处理分区点右侧的数据
        quickSort(array, q + 1, r);
    }

    /**
     * 我们通过游标 i 把 A[p…r-1]分成两部分。A[p…i-1]的元素都是小于 pivot 的，
     * 我们暂且叫它“已处理区间”，A[i…r-1]是“未处理区间”。我们每次都从未处理的区间
     * A[i…r-1]中取一个元素 A[j]，与 pivot 对比，如果小于 pivot，则将其加入到已
     * 处理区间的尾部，也就是 A[i]的位置。
     *
     * @param array 数组
     * @param p 起始位置
     * @param r 结束位置
     * @return 分区位置
     */
    public static int partition(int[] array, int p, int r) {
        // 选取最后一个作为分区点
        int pivot = array[r];
        int i = p;
        for (int j = p; j < r; j++) {
            if (array[j] < pivot) {
                // 其余数据与分区点数据比较,小于分区点的数据放到已处理区(正序排列,大于则是逆序排列)
                int tmp = array[j];
                array[j] = array[i];
                array[i++] = tmp;
            }
        }

        // 最终i的位置就是选取的分区点应该存在的位置
        int tmp = array[r];
        array[r] = array[i];
        array[i] = tmp;
        return i;

    }
}
